#pragma once

#include<iostream>
#include<assert.h>
#include<utility>

using namespace std;

namespace AVLTree
{
	template<class K,class V>
	class AVLNode
	{
	public:
		pair<K, V> _kv;
		AVLNode<K,V>* _left;
		AVLNode<K,V>* _right;
		AVLNode<K,V>* _parent;
		int _bf;

		AVLNode(const pair<K, V>& kv)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _kv(kv)
			, _bf(0)
		{}
		
	};

	template<class K,class V>
	class AVL
	{
		typedef AVLNode<K, V> Node;
	public:
		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return ture;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			if (kv.first > parent-kv.first)
			{
				parent->_right = cur;
			}
			else 
			{
				parent->_left = cur;
			}

			cur->_parent = parent;

			while (parent)
			{
				if(cur == parent->_left)
				{
					parent->_bf--;
				}
				else
				{
					parent->_bf++;
				}
				
				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_parent;
				}
				else if(parent->_bf == 2||parent->_bf == -2 )
				{
					if (cur->_bf == 1 || parent->_bf == 2)
					{
						RotateL(parent);
					}
					else if(parent->_bf == -2 || cur->_bf = -1)
					{
						RotateR(parent);
					}
				}
			}
		}

		void RotateL(Node* parent)
		{
			Node* cur = parent->_right;
			Node* curleft = cur->_left;

			parent->_left = curleft;

			if (curleft)
			{
				cur->_parent = parent;
			}

			cur->_left = parent;

			Node* ppndoe = parent->_parent;

			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->parent = nullptr;
			}
			else
			{
				if (ppndoe->_left == parent)
				{
					ppndoe->_left = cur;
				}
				else
				{
					ppndoe->_right = cur;

				}
				cur->_parent = ppndoe;

			}
			parent->_bf = cur->_bf = 0;



		}
		void RotateR(Node* parent)
		{
			Node* cur = parent->_right;
			Node* curright = cur->_right;

			parent->_right = curright;
			if (curright)
			{
				curright->_parent = parent;
			}

			cur->_left = parent;

			Node* ppnode = parent->_parent;

			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (ppnode->_left == parent)
				{
					ppnode->_left = cur;
				}
				else
				{
					ppnode->_right = cur;
				}
				cur->_parent = ppnode;
			}

			parent->_bf = cur->_bf = 0;

		}


	private:
		Node* _root = nullptr;
	};

}